package com.fosss.recursion;

/**
 * 使用递归回溯来走迷宫
 */
public class MiGong {
    public static void main(String[] args) {
        int[][] map=new int[8][7];
        //用1代表墙
        //将上下左右设为1
        for(int i = 0;i<8;i++){
            map[i][0]=1;
            map[i][6]=1;
        }
        for(int i = 0;i<7;i++){
            map[0][i]=1;
            map[7][i]=1;
        }
        //设置拦板
        map[3][1]=1;
        map[3][2] = 1;
        map[2][2]=1;
        map[1][2]=1;

        //输出地图
        for(int i = 0;i<8;i++){
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }

        boolean b = setMap(map, 2, 1);
        System.out.println(b?"能走通":"走不通");
        System.out.println();
        System.out.println("走完后的地图：");
        for(int i = 0;i<8;i++){
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }
    }

    /**
     * @param map 表示地图
     * @param i,j 表示从地图哪个位置出发
     * @return 返回是否找到了路
     * map[6][5]表示出口，i、j为0时表示没有走，1表示墙不能走，2为通路可以走，3表示已经走过但走不通
     * 走的方式：下->右->上->左
     */
    public static boolean setMap(int[][] map,int i,int j){
        if(map[6][5]==2){
            return true;
        }else {
            if(map[i][j]==0){//可以走
                map[i][j]=2;//假设可以走通！！！！！！！！！
                if(setMap(map,i+1,j)){//先向下走
                    return true;
                }else if (setMap(map, i, j+1)) {//向右走
                    return true;
                }else if(setMap(map,i-1,j)){//向上走
                    return true;
                }else if(setMap(map,i,j-1)){//向左走
                    return true;
                }else {
                    map[i][j] = 3;//都走不通，设置为3
                    return false;
                }
            }else {//map[i][j]为1/2/3
                return false;
            }
        }
    }


}














